Extensible grids: uniform sampling on a space-filling curve

摘要

We study the properties of points in $[0,1]^d$ generated by applyingHilbert's space-filling curve to uniformly distributed points in $[0,1]$. Fordeterministic sampling we obtain a discrepancy of $O(n^{-1/d})$ for $d\ge2$.For random stratified sampling, and scrambled van der Corput points, we get amean squared error of $O(n^{-1-2/d})$ for integration of Lipshitz continuousintegrands, when $d\ge3$. These rates are the same as one gets by sampling on$d$ dimensional grids and they show a deterioration with increasing $d$. Therate for Lipshitz functions is however best possible at that level ofsmoothness and is better than plain IID sampling. Unlike grids, space-fillingcurve sampling provides points at any desired sample size, and the van derCorput version is extensible in $n$. Additionally we show that certaindiscontinuous functions with infinite variation in the sense of Hardy andKrause can be integrated with a mean squared error of $O(n^{-1-1/d})$. It waspreviously known only that the rate was $o(n^{-1})$. Other space-fillingcurves, such as those due to Sierpinski and Peano, also attain these rates,while upper bounds for the Lebesgue curve are somewhat worse, as if thedimension were $\log_2(3)$ times as high.